Search results for "Indifference graph"
showing 9 items of 9 documents
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
On the chromatic number of disk graphs
1998
Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.
On Sturmian Graphs
2007
AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.
Some properties of vertex-oblique graphs
2016
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.
Algorithms on Graphs
1988
In this chapter we shall develop some basic algorithms for directed graphs and relations which will be of use in later chapters, where the efficient construction of parsers is considered. The constructions needed can be expressed as the computing of certain “relational expressions”. These are expressions whose operands are relations and whose operators are chosen from among multiplication, closure, union and inverse. For this purpose we need to develop an algorithm for computing the closure of a relation. In view of the nature of our applications, the most appropriate way to do this is by a depth-first traversal of the graph that corresponds to the given relation. Other ways of computing th…
Spatial Search by Quantum Walk is Optimal for Almost all Graphs.
2015
The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erd\"os-Renyi random graphs, i.e.\ graphs of $n$ vertices where each edge exists with probability $p$, search by CTQW is \textit{almost surely} optimal as long as $p\geq \log^{3/2}(n)/n$. Consequently, we show that quantum spatial search is in fact optimal for \emph{almost all} graphs, meaning that the fraction of graphs of $n$ vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by provin…